package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC959 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 好家伙，直接并查集
     * @return:
     */
    class Solution {
        public int regionsBySlashes(String[] grid) {
            int n = grid.length;
            int[] f = new int[n * n * 4];
            for (int i = 0; i < n * n * 4; i++) {
                f[i] = i;
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int idx = i * n + j;
                    if (i < n - 1) {
                        int bottom = idx + n;
                        merge(f, idx * 4 + 2, bottom * 4);
                    }
                    if (j < n - 1) {
                        int right = idx + 1;
                        merge(f, idx * 4 + 1, right * 4 + 3);
                    }
                    if (grid[i].charAt(j) == '/') {
                        merge(f, idx * 4, idx * 4 + 3);
                        merge(f, idx * 4 + 1, idx * 4 + 2);
                    } else if (grid[i].charAt(j) == '\\') {
                        merge(f, idx * 4, idx * 4 + 1);
                        merge(f, idx * 4 + 2, idx * 4 + 3);
                    } else {
                        merge(f, idx * 4, idx * 4 + 1);
                        merge(f, idx * 4 + 1, idx * 4 + 2);
                        merge(f, idx * 4 + 2, idx * 4 + 3);
                    }
                }
            }

            Set<Integer> fathers = new HashSet<Integer>();
            for (int i = 0; i < n * n * 4; i++) {
                int fa = find(f, i);
                fathers.add(fa);
            }
            return fathers.size();
        }

        public int find(int[] f, int x) {
            if (f[x] == x) {
                return x;
            }
            int fa = find(f, f[x]);
            f[x] = fa;
            return fa;
        }

        public void merge(int[] f, int x, int y) {
            int fx = find(f, x);
            int fy = find(f, y);
            f[fx] = fy;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC959 an = new LC959();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
